package leetcode_900;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *@author 周杨
 *MakingALargeIsland_827_ 给定一个二维矩阵 表示岛和海 问最多将一个海变成岛  那么最大的岛面积是多少
 *describe:用深度优先搜索和填充 将一块连续的岛上色 map保存该颜色的大小 AC 34%
 *2018年10月30日 下午1:53:33
 */
public class MakingALargeIsland_827_ {
	public static void main(String[] args) {
		MakingALargeIsland_827_ test=new MakingALargeIsland_827_();
		int[][]grid=new int[][] {{1,1,1},{1,1,0},{1,0,0}};
		System.out.println(test.largestIsland(grid));
	}
	
	int[][]grid;
	int color=2;
	public int largestIsland(int[][] grid) {
        this.grid=grid;
        int res=0;
        int maxArea=0;
        Map<Integer,Integer> colorMap=new HashMap<Integer,Integer>();
        colorMap.put(0, 0);//默认没有
        for(int i=0;i<grid.length;++i) {
        	for(int j=0;j<grid[0].length;++j) {
        		if(grid[i][j]==1) {
        			int num=help(i,j);
        			maxArea=Math.max(maxArea, num);
        			colorMap.put(color, num);
        			++color;
        		}
        	}
        }
        for(int i=0;i<grid.length;++i) {
        	for(int j=0;j<grid[0].length;++j) {
        		if(grid[i][j]==0) {
        			int count=0;
        			Set<Integer> visited=new HashSet<Integer>();
        			if(i>0) {
        				count+=colorMap.get(grid[i-1][j]);
        				visited.add(grid[i-1][j]);
        			}
        			if(j>0) {
        				if(!visited.contains(grid[i][j-1])) {
        					count+=colorMap.get(grid[i][j-1]);
        					visited.add(grid[i][j-1]);
        				}
        			}
        			if(i!=grid.length-1) {
        				if(!visited.contains(grid[i+1][j])) {
        					count+=colorMap.get(grid[i+1][j]);
        					visited.add(grid[i+1][j]);
        				}
        			}
        			if(j!=grid[0].length-1) {
        				if(!visited.contains(grid[i][j+1])) {
        					count+=colorMap.get(grid[i][j+1]);
        				}
        			}
        			res=Math.max(res, count);
        		}
        	}
        }
        return Math.max(maxArea, res+1);
    }
	
	public int help(int x,int y) {
		if(x<0||y<0||x==grid.length||y==grid[0].length
				||grid[x][y]==0||grid[x][y]==color)
			return 0;
		grid[x][y]=color;
		return 1+help(x+1,y)+help(x-1,y)+help(x,y+1)+help(x,y-1);
	}	
}
